package dfs;

/**
 * leet-code(494) 目标和
 *
 * @author Ringo
 * @date 2022/2/6 22:04
 */
public class TargetSum {

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 1, 1};
        System.out.println(findTargetSumWays(nums, 3));
    }

    // 1. 递归
    public static int findTargetSumWays(int[] nums, int target) {
        return dfs(nums, target, 0, 0);
    }

    public static int dfs(int[] nums, int target, int index, int cur) {
        if (index == nums.length) {
            return cur == target ? 1 : 0;
        }
        int left = dfs(nums, target, index + 1, cur + nums[index]);
        int right = dfs(nums, target, index + 1, cur - nums[index]);
        return left + right;
    }

}
